package com.xj.algorithm.leetcode;

import static java.lang.Math.sqrt;

/**
 * x的平方根
 */
public class L69_整数的平方根 {

    /**
     * 实现 int sqrt(int x) 函数。
     * <p>
     * 计算并返回 x 的平方根，其中 x 是非负整数。
     * <p>
     * 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
     * <p>
     * 示例 1:
     * 输入: 4
     * 输出: 2
     * <p>
     * 示例 2:
     * 输入: 8
     * 输出: 2
     * 说明: 8 的平方根是 2.82842...,
     *      由于返回类型是整数，小数部分将被舍去。
     */

    public static void main(String[] args) {
        System.out.println(mySqrtGood(4));
        System.out.println(mySqrtGood(8));
        System.out.println(mySqrtGood(1));
        System.out.println(mySqrtGood(2147483647));
    }

    //自己的解法1：直接使用api
    public static int mySqrtAPI(int x) {
        return (int) sqrt(x);
    }

    //自己的解法2：从一半的地方开始处理,有溢出风险
    public static int mySqrt(int x) {
        int left = 0, right = x;
        int mid = (left + right) / 2;
        while (left <= right) {
            if ((long) mid * mid > x) {
                right = mid - 1;
                mid = (left + right) / 2;
            } else if ((long) mid * mid < x) {
                left = mid + 1;
                mid = (left + right) / 2;
            } else {
                break;
            }
        }
        return mid;
    }

    //精彩解法：牛顿法:本质是使x/mid 约等于mid。高数的知识
    public static int mySqrtGood(int x) {
        long mid = x;
        while (mid * mid > x) {
            mid = (mid + x / mid) / 2;
        }
        return (int) mid;
    }

}
